/*
 * @lc app=leetcode.cn id=440 lang=golang
 *
 * [440] 字典序的第K小数字
 */

// @lc code=start
func findKthNumber(n int, k int) int {
	cur := 1
	for {
		count := getCount(cur, n)
		if k > count {
			cur = cur + 1
			k = k - count
		} else {
			if k > 1 {
				cur *= 10
				k--
			} else {
				break
			}
		}
	}
}

func getCount(i int, n int) int {
	next := i + 1
	count := 0
	for i <= n {
		count += min(n, next-1) - i + 1
		next *= 10
		i *= 10
	}
	return count
}

// @lc code=end

